/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***给定一个字符串，创建赫夫曼编码                ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
#include <map>
#include <cstdlib>
#include <cstring>
//字节输入输出流
#include <sstream>
// c++中 std::sort 需要能够有可供速记访问的迭代器
//而list容器实现方法是链表，因为不具有该属性，也就不能使用std::sort排序
// list容器排序使用list::sort();
using std::cout;
using std::endl;
using std::list;
using std::map;
using std::string;
using std::vector;

class Node
{
public:
    //删除默认构造
    Node() = delete;

    //两种构造函数
    Node(char data, int value) : data(data), value(value), left(nullptr), right(nullptr) {}
    Node(char data, int value, Node *left, Node *right) : data(data), value(value), left(left), right(right) {}
    //供算法调用的函数，一定要重载<运算符，系统默认使用<
    bool operator<(Node &node)
    {
        return value < node.value;
    }
    //排序使用的 谓词
    static bool lessThan(Node *node1, Node *node2)
    {
        return node1->value < (node2->value);
    }
    int getData()
    {
        return data;
    }
    int getValue()
    {
        return value;
    }
    Node *getLeft()
    {
        return left;
    }
    Node *getRight()
    {
        return right;
    }
    //将对象转化为字符串
    string transToString()
    {
        string resStr("char= weight=");
        resStr.insert(resStr.begin() + 5, this->data);
        resStr.append(std::to_string(this->value));
        return resStr;
    }
    //二叉树的前序遍历
    void preOrder(Node *node)
    {
        if (node == nullptr)
        {
            cout << "赫夫曼树为空" << endl;
        }
        cout << node->transToString() << "\t";
        if (node->left != nullptr)
        {
            preOrder(node->left);
        }
        if (node->right != nullptr)
        {
            preOrder(node->right);
        }
    }
    //重载preOrder，使其避免传入参数
    void preOrder()
    {
        preOrder(this);
    }
    ~Node()
    {
        Node *tempNode = this;
        if (tempNode->left != nullptr)
        {
            delete tempNode->left;
        }
        if (tempNode->right != nullptr)
        {
            delete tempNode->right;
        }
        if (tempNode != nullptr)
        {
            delete tempNode;
            tempNode = nullptr;
        }
    }

private:
    /*data 存放字符  weight 存放权重  left 左子节点 right 右子节点*/
    char data;
    int value;
    Node *left;
    Node *right;
};

class HuffmanCode
{
public:
    /*传入霍夫曼树的根节点  通过调用函数，构造map<char, string>*/
    HuffmanCode(string oriStr) : oriStr(oriStr)
    {
        //生成权重表
        charMap = new map<char, int>();
        strToMap(this->oriStr);
        //生成赫夫曼树，并且让root指向根节点
        root = createHuffmanTree(this->charMap);
        //生成赫夫曼编码
        huffmanCodeMap = new map<char, string>();
        getHuffmanCode(root, "");
        //初始化 vector<uint8_t>
        charVec = new vector<uint8_t>;
    }
    //删除拷贝构造函数和移动构造函数
    HuffmanCode(HuffmanCode &) = delete;
    HuffmanCode(HuffmanCode &&) = delete;
    /*
    功能：对压缩功能的进一步封装
    参数：无
    返回值：压缩之后的 vector<uint8_t>
    */
    vector<uint8_t> &huffmanZip()
    {
        zip();
        return (*charVec);
    }
    map<char, string> getHuffCodeMap()
    {
        return *(this->huffmanCodeMap);
    }
    /*
    功能：将一个8位 bit转化为  对应的字符串
    参数：传入 一个8位 Byte
    返回值：转换好的字符串
    */
    static string byteToStr(uint8_t byte)
    {
        string resStr(8, '0');
        for (int i = 0; i < 8; i++)
        {
            //判断uint8_t的第i位的数值
            if (byte & (1 << i))
            {
                resStr[7 - i] = '1';
            }
            else
            {
                resStr[7 - i] = '0';
            }
        }
        return resStr;
    }

    //打印类的值
    void printCode()
    {
        for (auto item : (*huffmanCodeMap))
        {
            cout << "char:" << item.first << "\t"
                 << "huffmancode:" << item.second << endl;
        }
    }
    /*
    作用：传入string，传出利用map统计字符的字符数
    参数：oriStr  传入的原始字符串
    返回值：void
    */
    void strToMap(const string &oriStr)
    {
        for (auto item : oriStr)
        {
            if (charMap->count(item) == 0)
            {
                // make_pair不需要声明变量的类型
                charMap->insert(std::make_pair(item, 1));
                // resMap->insert(std::pair<char, int>(item, 1));
            }
            else
            {
                (*charMap)[item]++;
            }
        }
    }

    //重载getCodeMap函数，实现无参调用
    inline map<char, string> getCodeMap()
    {
        return (*this->huffmanCodeMap);
    }
    /*
    作用：利用赫夫曼树递归生成赫夫曼编码  并将编码放入map<char, string> 容器中
    参数：node 将要递归的节点   tempCode 用于循环凭借的字符串
    返回值：空
    */
    void getHuffmanCode(Node *node, const string preCode)
    {
        if (node == nullptr)
        {
            cout << "当前赫夫曼树的根节点为空" << endl;
        }
        //调用拷贝构造函数

        //从根节点开始递归，获取霍夫曼编码
        //说明是  非叶子节点
        if (node->getData() == '\0')
        {
            if (node->getLeft() != nullptr)
            {
                string tempCode(preCode);
                tempCode.append("0");
                getHuffmanCode(node->getLeft(), tempCode);
            }
            if (node->getRight() != nullptr)
            {
                string tempCode(preCode);
                tempCode.append("1");
                getHuffmanCode(node->getRight(), tempCode);
                // preCode.clear();
            }
        }
        //如果是叶子节点，向map中插入编码，清空str，递归结束
        if (node->getData() != '\0')
        {
            huffmanCodeMap->insert(std::make_pair(node->getData(), preCode));
            return;
        }
    }
    /*
    作用：传入 map<char, int> ，传出一个赫夫曼树的根节点
    参数：map<char, int> 字符和字符出现的次数
    返回值：创建的赫夫曼树的根节点
    */
    Node *createHuffmanTree(map<char, int> *strMap)
    {
        //生成一个承载所有 node的 list容器
        list<Node *> listNode;
        for (auto item : *strMap)
        {
            listNode.push_back(new Node(item.first, item.second));
        }
        while (listNode.size() > 1)
        {
            //对容器的元素进行排序，对类进行排序， 可以重载< 或者定义静态函数 作为谓词
            listNode.sort(Node::lessThan);
            //从列表中取出最小的两个节点，并且创建两个子节点的父节点
            auto leftNode = listNode.front();
            listNode.pop_front();
            auto rightNode = listNode.front();
            listNode.pop_front();
            Node *parent(new Node('\0', leftNode->getValue() + rightNode->getValue(), leftNode, rightNode));
            //父节点，重新加入队列
            listNode.push_front(parent);
        }
        auto node = listNode.front();
        return node;
    }
    /*
    作用：数据压缩函数
    参数：oriStr 想要压缩的字符串  map<char, string> 赫夫曼编码的容器
    返回值：创建的赫夫曼树的根节点
    */
    void zip()
    {
        //首先按照huffmanCode得到使用编码编译之后的二进制字符串
        auto strLen = oriStr.length();
        //需要按照每8个字节数分组
        //将二进制字符串转化为 vector<char> 从而实现压缩
        string binaryStr;
        for (size_t i = 0; i < strLen; i++)
        {
            //得到二进制字符串
            binaryStr.append((*huffmanCodeMap)[oriStr[i]]);
        }
        // cout<<"binaryStr="<<binaryStr<<endl;
        // cout<<"binaryStr.size()="<<binaryStr.size()<<endl;
        auto binStrLen = binaryStr.length();
        size_t len = (binaryStr.size() + 7) / 8;
        // vector<uint8_t> charVec;
        charVec->reserve(len + 1);
        string tempStr;
        for (size_t i = 0; i < len; i += 1)
        {
            //截取字符串
            // cout<<"i="<<i<<endl;
            if ((8 * i + 8) > binStrLen)
            {
                tempStr = binaryStr.substr(i * 8, binStrLen - i * 8);
            }
            else
            {
                tempStr = binaryStr.substr(i * 8, 8);
            }
            uint8_t u8Num = (std::stoi(tempStr, 0, 2)) & (0xff);
            charVec->push_back(u8Num);
        }
        //因为最后一个字符串有可能不足8位，而压缩之后，无法判断其位数
        //所以需要将最后一个字符串的长度压入vector
        charVec->push_back((uint8_t)tempStr.size());
        // cout<<"tempStr="<<tempStr<<endl;
    }
    /*
    功能：解压数据   写为类内的静态函数
    参数：使用uint8_t填充的vector，解码使用map<char, string>
    返回值：解压之后的字符串
    */
    static string unzip(const vector<uint8_t> &byteVec, map<char, string> huffmanMap)
    {

        //将byteVec中存储的byteVec转化为  010101....组成的字符串
        string binaryStr;
        auto length = byteVec.size();
        //前 length-2个数值  都是满8位的之间转换
        for (size_t i = 0; i < length - 1; i++)
        {
            if (i == (length - 2))
            {
                binaryStr.append(byteToStr(byteVec[i]).substr((8 - byteVec[length - 1]), byteVec[length - 1]));
                break;
            }
            binaryStr.append(byteToStr(byteVec[i]));
        }
        //测试代码，测试转化的二进制字符串是否符合要求
        // cout << "binaryStr=" << endl;
        // for (size_t i = 0; i < binaryStr.length(); i += 8)
        // {
        //     if ((i + 8) > (binaryStr.length() - 1))
        //     {
        //         cout << binaryStr.substr(i, binaryStr.length() - i) << endl;
        //         break;
        //     }
        //     cout << binaryStr.substr(i, 8) << endl;
        // }
        // cout << "end of binaryStr" << endl;
        //将上面得到的二进制字符串转化为 原始的字符串
        map<string,char> backHuffmanMap;
        //得到逆向的编码
        for(auto& item:huffmanMap){
            backHuffmanMap.insert(std::make_pair(item.second,item.first));    
        }
        string resStr;
        size_t len=binaryStr.length();
        for(size_t i=0;i<len;){
            size_t count=1;
            //一直到匹配到  map容器中的一个  key为止
            while(backHuffmanMap.count(binaryStr.substr(i,count))==0){
                count++;
            }//将查询到的内容，加入返回字符串中
            resStr.append(1,backHuffmanMap[binaryStr.substr(i,count)]);
            i+=count;
        }
        return resStr;
    }

    ~HuffmanCode()
    {
        if (charMap != nullptr)
        {
            delete charMap;
            charMap = nullptr;
        }
        if (root != nullptr)
        {
            delete root;
            root = nullptr;
        }
        if (charVec != nullptr)
        {
            delete charVec;
            charVec = nullptr;
        }
    }

private:
    //原始字符串
    string oriStr;
    //字符  和  字符次数权重表
    map<char, int> *charMap;
    //霍夫曼树的根节点
    Node *root;
    // map<char, string> 容器，储存字符和对应的霍夫曼编码
    map<char, string> *huffmanCodeMap;
    //压缩之后的数据
    vector<uint8_t> *charVec;
};

int main()
{
    string oriStr("i like like like java do you like a java");
    HuffmanCode *huffZip = new HuffmanCode(oriStr);
    vector<uint8_t> resVec = huffZip->huffmanZip();
    // for (auto item : resVec)
    // {
    //     cout << item + 0 << "\t";
    // }
    map<char, string> charMap(huffZip->getHuffCodeMap());
    cout<<HuffmanCode::unzip(resVec, charMap)<<endl;
    // cout << HuffmanCode::byteToStr((uint8_t)100) << endl;
    // cout << HuffmanCode::byteToStr((uint8_t)200) << endl;

    if (huffZip != nullptr)
    {
        delete huffZip;
        huffZip = nullptr;
    }
    return 0;
}